package com.huangyi;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        //存在重复元素II
        class Solution {
            public boolean containsNearbyDuplicate(int[] nums, int k) {
                Map<Integer, Integer> last = new HashMap<>();
                for (int i = 0; i < nums.length; i++) {
                    int x = nums[i];
                    if (last.containsKey(x)) {
                        int prev = last.get(x);
                        if (i - prev <= k) return true;
                    }
                    // 不论是否命中，都更新为“最近一次出现”
                    last.put(x, i);
                }
                return false;
            }
        }


        //母异位词分组
        class Solution2 {
            public List<List<String>> groupAnagrams(String[] strs) {
                Map<String, List<String>> map = new HashMap<>();
                for (String s : strs) {
                    char[] ch = s.toCharArray();
                    Arrays.sort(ch);                 // O(L log L)
                    String key = new String(ch);     // 规范化表示
                    map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
                }
                return new ArrayList<>(map.values());
            }
        }

    }
}